/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package progentiere.knapsackprb;


public class DPInteger extends Algorithm 
{
    
    @Override
    Solution solve(KnapSackProblem problem) 
    {
        int N = problem.getNbItems();
        int W = (int)problem.getCapacity();
        
        Solution optSol = new Solution(N);
        
        int[][] opt = new int[N][W];
        boolean[][] sol = new boolean[N][W];

        for (int k = 1; k < N; k++) {
            for (int w = 1; w < W; w++) {

                // don't take item n
                int option1 = opt[k-1][w];

                // take item n
                int option2 = Integer.MIN_VALUE;
                if ((int)problem.getItems().get(k).getWeight() <= w)
                {
                    option2 = (int)problem.getItems().get(k).getProfit() + opt[k-1][w-(int)problem.getItems().get(k).getWeight()];
                }

                // select better of two options
                opt[k][w] = Math.max(option1, option2);
                sol[k][w] = (option2 > option1);
            }
        }
        
        boolean[] take = new boolean[N+1];
        for (int k = N-1, w = W-1; k > 0; k--) {
            if (sol[k][w]) 
            { 
                optSol.getContent()[k] = 1.0;
                w = w - (int)problem.getItems().get(k).getWeight(); 
            }
            else 
            { 
                optSol.getContent()[k] = 0.0;                  
            }
        }
        
        return optSol;
    }

}
